✎ Résoudre une équation diophantienne - Méthode

Soit \(a\) , \(b\)  et \(c\) trois entiers relatifs non nuls. Soit  \((E) \colon ax+by=c\)  d'inconnue \((x;y) \in \mathbb{Z}^2\) .

Pour résoudre l'équation \((E)\) , on suit les étapes suivantes.

• Étape 1 On applique l'algorithme d'Euclide pour calculer \(\mathrm{PGCD}(a;b)\) et savoir si \((E)\) admet des solutions.
  
• Étape 2 Si \((E)\) admet des solutions, on remonte l'algorithme d'Euclide pour en trouver une solution particulière \((x_0;y_0)\) .
  Attention : il ne faut pas oublier que le second membre de  \((E)\)  est \(c\) , qui n'est a priori pas égal à  \(\mathrm{PGCD}(a;b)\) .
  
• Étape 3 On choisit une solution quelconque \((x;y)\) de \((E)\) , on remarque que
  \(ax+by=ax_0+by_0 \ \ \Longleftrightarrow \ \  a(x-x_0)=b(y_0-y)\)  et on utilise le théorème de Gauss pour en déduire \(x\) et \(y\) .
  Attention : si \(a\) et \(b\) ne sont pas premiers entre eux, on divise d'abord l'égalité ci-dessus par \(\mathrm{PGCD}(a;b)\) pour pouvoir utiliser le théorème de Gauss.
  
• Étape 4 On vérifie que les couples \((x;y)\) trouvés sont solutions de \((E)\) .
  
• Étape 5 On conclut.